package arithmetic1.sort;

import java.text.SimpleDateFormat;
import java.util.Date;

/*
    希尔排序:
        先将待排序列分成length/2个子序列,对每个子序列分别进行插入排序
        在将待排序列分成length/2/2个子序列，对每个子序列再分别进行插入排序
        依此类推，直到length/2/2../2=1时，再对这个序列进行插入排序
 */
public class ShellSort {
    public static void main(String[] args) {
//        int arr[]={6,3,2,4,7,9,0,5,1,0,20,5,};

        int arr[] = new int[8000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 800000);
        }

        Date date = new Date();
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd hh:mm:ss");
        String time1 = sdf.format(date);
        System.out.println("排序前的时间:" + time1);

        shellSort(arr);

        date = new Date();
        String time2 = sdf.format(date);
        System.out.println("排序后的时间:" + time2);

//        System.out.println(Arrays.toString(arr));
    }

    /**
     * 希尔排序
     */
    public static void shellSort(int[] arr) {
        int n = 2;
        while (arr.length / n >= 1) {    //将子序列进行插入排序
            //记录步长
            int step = arr.length / n;
            //将该序列划分为length/n个子序列
            for (int i = 0; i < step; i++) {
                //对每个子序列进行插入排序
                insertSort(arr, step, i);
            }
            n *= 2;
        }
    }

    /**
     * 对每个子序列进行插入排序  该子序列下标在arr中满足的要求为：从第n个开始，每次增加step
     *
     * @param arr
     * @param step
     * @param start
     */
    public static void insertSort(int[] arr, int step, int start) {
        for (int i = start; i < start + step * (arr.length / step - 1); i += step) {
            //记录要插入的数
            int temp = arr[i + step];
            //记录要插入的位置, 默认为它本身的位置
            int index = i + step;
            for (int j = i; j >= start; j -= step) {
                if (temp < arr[j]) {
                    //将大的数后移
                    arr[j + step] = arr[j];
                    //下标前移
                    index -= step;
                } else {
                    break;
                }
            }
            //将待插入的数插入到index这个位置
            arr[index] = temp;
        }
    }
}
